package cxydmmszl.tmp.t6.middle;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * <li style="color: red;">Prob</li>
 * Manacher 算法
 * <li style="color: green;">Desc</li>
 * 给定一个字符串 str, 返回 str 中最长回文子串的长度
 * <br/><br/>[举例]<br/>
 * str=“123”。其中的最长回文子串“1”或者“2”或者“3”，所以返回1。<br/>
 * str=“abc1234321ab”。其中的最长回文子串“1234321”，所以返回7。
 * <br/><br/>[要求]<br/>
 * 如果 str 的长度为 N，解决原问题的时间复杂度都达到 O(N)。
 * <br/><br/>备注：<br/>
 * 设 N 表示输入字符串的长度<br/>
 * 保证输入字符中只含有小写字母及数字<br/>
 * 1⩽N⩽5∗10^5
 * <li style="color: green;">Input</li>
 * 输入为一个字符串str
 * <li style="color: green;">Output</li>
 * 输出一个整数表示最长回文子串的长度
 * <li style="color: blue;">Link</li> CD85
 *
 * @author habitplus
 * @since 2021-11-02 22:40
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();

        int len = maxLengthOfPalindrome(str);
        System.out.println(len);
    }

    private static int maxLengthOfPalindrome(String str) {
        if (str == null || str.length() < 1) return 0;
        // 对原字符数组进行预处理：插入特殊辅助字符
        char[] chs = manacherString(str);
        int n = chs.length;
        // pArr[i] 表示 以 chs[i] 为回文中心，扩出去的得到的最大回文半径
        int[] pArr = new int[n];
        // 目前遍历到的字符的所有回文半径中，最右即将到达的位置下标
        int pR = -1;
        // 最近一次更新 pR 时，那个回文中心的位置下标
        int index = -1;

        int maxLen = 0;
        for (int i = 0; i < n; i++) {
            pArr[i] = pR > i ? Math.min(pArr[2 * index - i], pR - i) : 1;
            while (pArr[i] + i < n && i  - pArr[i] > -1) {
                if (chs[i + pArr[i]] == chs[i - pArr[i]]) pArr[i]++;
                else break;
            }

            if (i + pArr[i] > pR) {
                // 要更新 pR
                pR = pArr[i] + i;
                index = i;
            }
            maxLen = Math.max(pArr[i], maxLen);
        }

        return maxLen - 1;
    }

    private static char[] manacherString(String str) {
        char[] ch = str.toCharArray();
        char[] res = new char[ch.length * 2 + 1];
        int j = 0;
        for (int i = 0; i < res.length; i++) {
            res[i] = (i & 1) == 0 ? '#' : ch[j++];
        }
        return res;
    }
}
